package code;

import java.util.ArrayList;
import java.util.List;


public class Permutations {
	
	public void dfs(int n,int step,int[] path,boolean[] used,List<Integer> list){
		if(step==n){
			int number=0;
			for(int i=0;i<step;i++){
				number*=10;
				number+=path[i];
			}
			list.add(number);
//			System.out.println(number);
			return;
		}
		for(int i=1;i<=n;i++){
			if(!used[i]){
				used[i]=true;
				path[step]=i;
				dfs(n,step+1,path,used,list);
				used[i]=false;
			}
		}
	}
    public String getPermutation(int n, int k) {
    	List<Integer> list=new ArrayList<Integer>();
    	boolean[] used=new boolean[n+1];
    	int[] path=new int[n];
    	dfs(n,0,path,used,list);
    	if(k==0 || k==list.size())	return null;
        int ans=list.get(k-1);
        return String.valueOf(ans);
    }
    public int sqrt(int x){
    	if(x==0)	return 0;
    	int ans,l,r,mid;
    	l=1;
    	r=1<<16;
    	ans=1;
        while(l<r){
        	mid=l+r>>1;
        	long n=(long)(mid)*mid;
        	if(n<=x){
        		ans=mid;
        		l=mid+1;
        	}
        	else r=mid-1;
        }
        if((long)(l)*l<=x)	ans=l;
        return ans;
    }
    /*
     * 用模拟的方法，求n!的第k个排列，显然会超时
     * 所以，直接生成第k个排列的方法
     * n!生成的过程
     * x(n-1)，确定了第一个数之后，剩下的就是有(n-1)!个数
     * xy(n-2),同理，确定了2位之后，剩下的就有(n-2)!个数
     * 我们可以这样来求第k的排列
     * 第一位：(k-1)/(n-1)!,这就是第一位数
     * 第二位：(k-1)%(n-1)!,就是第二位数（从小到大，但是要挖掉已经用过的第一位数）
     */
    public String getPermutationII(int n, int k) {
    	List<Integer> list=new ArrayList<Integer>();
    	boolean[] used=new boolean[n+1];
    	StringBuilder sb=new StringBuilder();
    	int i,j;
    	int[] permutation=new int[n+1];
    	List<Integer> digital=new ArrayList<Integer>();
    	permutation[0]=1;
    	permutation[1]=1;
    	for(i=1;i<=n;i++){
    		permutation[i]=i*permutation[i-1];
    		digital.add(i);
    	}
    	k--;
    	for(i=1;i<=n;i++){
    		int idx=k/permutation[n-i];
    		sb.append(digital.get(idx));
    		digital.remove(idx);
    		k=k%permutation[n-i];
    	}
        return sb.toString();
    }
    
    public void nextPermutation(int[] num) {
    	int i,j,k;
    	int n=num.length;
    	if(n<=1)	return;
    	for(i=1;i<n;i++){
    		if(num[i-1]<num[i])	break;
    	}
    	if(i==n){
    		for(i=0;i<n/2;i++){
    			int tmp=num[i];
    			num[i]=num[n-i-1];
    			num[n-i-1]=tmp;
    		}
    		return;
    	}
    	int min;
    	int idx=0;
    	for(i=n-2;i>=0;i--){
    		min=Integer.MAX_VALUE;
    		for(j=i+1;j<n;j++){
    			if(num[i]<num[j] && num[j]<min){ 
    				min=num[j];
    				idx=j;
    			}
    		}
    		if(min<Integer.MAX_VALUE){
	    		int tmp=num[idx];
	    		num[idx]=num[i];
	    		num[i]=tmp;
	    		for(j=i+1;j<n;j++)
	    			for(k=j+1;k<n;k++){
	    				if(num[j]>num[k]){
	    		    		tmp=num[j];
	    		    		num[j]=num[k];
	    		    		num[k]=tmp;
	    				}
	    			}
	    		break;
    		}
    	}
    }
    /*
     * java通过下面的swap函数是不能实现交换参数a,b的值的。出了函数之后，a，b值是没有交换的。
     * 因为这个与jvm有关，传入的是基本类型int，a,b。他们是作为参数变量的副本被压入栈中计算。
     * 所以计算完之后，函数调用结束之后，a，b副本的值，改变了。但是a,b的值，还是原来的值。
     * 但是，如果传入的是对象的话，a,b是作为引用，传入。所以，函数调用完之后，可以实现对象的效果
     */
    public void swap(int a,int b){
    	int tmp=a;
    	a=b;
    	b=tmp;
    }
    public static void main(String[] args){
    	Permutations ps=new Permutations();
    	int[] num={1,1,5};
    	ps.nextPermutation(num);
    	for(int i=0;i<num.length;i++){
    		System.out.print(num[i]+" ");
    	}
    	System.out.println();
    }
}
